package com.kehao.leetcode.middle.backtracking_algorithm;

import org.junit.Test;

import javax.xml.crypto.dsig.keyinfo.RetrievalMethod;

public class WordSearchSolution {

    public boolean exist(char[][] board, String word) {
        char[] chars = word.toCharArray();
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j]==chars[0]){
                    if(exist(board,chars,1,i,j,visited)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean exist(char[][] board, char[] word, int indexOfWord, int i, int j,boolean[][] visited) {
        boolean existUp = false;
        boolean existDown = false;
        boolean existLeft = false;
        boolean existRight = false;
        if(visited[i][j]) return false;
        if(indexOfWord == word.length) return true;
        else visited[i][j] = true;
        if(i>0&&board[i-1][j]==word[indexOfWord]) existUp = exist(board,word,indexOfWord+1,i-1,j,visited);
        if(existUp) {
            visited[i][j] = false;
            return true;
        }
        if(i<board.length-1&&board[i+1][j]==word[indexOfWord]) existDown = exist(board,word,indexOfWord+1,i+1,j,visited);
        if(existDown) {
            visited[i][j] = false;
            return true;
        }
        if(j>0&&board[i][j-1]==word[indexOfWord]) existLeft = exist(board,word,indexOfWord+1,i,j-1,visited);
        if(existLeft){
            visited[i][j] = false;
            return true;
        }
        if(j<board[0].length-1&&board[i][j+1]==word[indexOfWord]) existRight = exist(board,word,indexOfWord+1,i,j+1,visited);
        if(existRight) {
            visited[i][j] = false;
            return true;
        }
        else {
            visited[i][j] = false;
            return false;
        }
    }

    @Test
    public void test01(){
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word = "SEE";
        System.out.println(exist(board, word));
    }

    @Test
    public void test02(){
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word = "ABCB";
        System.out.println(exist(board, word));
    }
}
